package com.lizk.sort;

import java.util.Random;

public class QuickSort {
    public static Integer[] sort(Integer[] arrays) {
        deal(arrays,0,arrays.length-1);
        return arrays;
    }

    public static Integer[] sort2(Integer[] arrays) {
        deal2(arrays,0,arrays.length-1);
        return arrays;
    }

    public static Integer[] sort3(Integer[] arrays) {
        //SortUtils.print(arrays);
        deal3(arrays,0,arrays.length-1);
        return arrays;
    }

    /**
     * 基本的处理
     * 1.每次以数组第一个元素为基准，然后依次比较后面的元素与它的大小
     * 2.如果后面的元素比第一个元素大，那么不做处理
     * 3.如果后面的元素比第一个元素小，那么把元素交换到第一个元素的后面的位置，记录分隔索引数字自增1
     * 4.当整个数组都处理完以后，那么把第一个元素与分隔索引位置的元素交换
     * @param arrays    要排序的数组
     * @param begin     处理排序的开始位置
     * @param end       处理排序的结束位置
     */
    public static void deal(Integer [] arrays , int begin , int end){

        if(begin >= end){
            return;
        }
        int v = arrays[begin];
        int mid = begin+1;
        for (int i = begin + 1; i <= end; i++) {
            if(arrays[i] < v){
                SortUtils.swap(arrays,i,mid);
                mid ++;
            }
        }
        SortUtils.swap(arrays,begin,mid-1);
        deal(arrays,begin,mid-2);
        deal(arrays,mid,end);
    }

    /**
     * 第一版优化操作，针对几乎有序的数组进行优化
     * 优化思路：
     *      因为有序数组每次拆分的数组都是上一次数组长度减1，所以整个递归的深度就是数组的长度，算法是On^2复杂度的算法
     *      为了使拆分的数组尽量均匀，选取基准元素的时候，使用随机数的形式
     * @param arrays    要排序的数组
     * @param begin     处理排序的开始位置
     * @param end       处理排序的结束位置
     */
    static Random random = new Random();
    public static void deal2(Integer [] arrays , int begin , int end){

        if(begin >= end){
            return;
        }
        //这里通过随机数随便选择一个位置，然后把随机位置的元素交换到第一个位置，后续排序处理不变

        int randomIndex = random.nextInt(end -begin + 1 ) + begin;
        SortUtils.swap(arrays,begin,randomIndex);

        int v = arrays[begin];
        int mid = begin+1;
        for (int i = begin + 1; i <= end; i++) {
            if(arrays[i] < v){
                SortUtils.swap(arrays,i,mid);
                mid ++;
            }
        }
        SortUtils.swap(arrays,begin,mid-1);
        deal2(arrays,begin,mid-2);
        deal2(arrays,mid,end);
    }

    /**
     * 第二版优化操作，数组中有大量重复元素的优化
     * 优化思路：
     *      当数组中有大量的重复元素的时候，由于大于等于基准元素的时候不做处理，所以等于基准元素的数据都堆积在大于基准元素的位置，造成拆分数组不均匀。
     *      优化的时候大于基准元素的，把大于基准元素的元素交换到数组的末尾
     *
     * @param arrays    要排序的数组
     * @param begin     处理排序的开始位置
     * @param end       处理排序的结束位置
     */
    public static void deal3(Integer [] arrays , int begin , int end){

        if(begin >= end){
            return;
        }
        //这里通过随机数随便选择一个位置，然后把随机位置的元素交换到第一个位置，后续排序处理不变

        int randomIndex = random.nextInt(end -begin + 1 ) + begin;
        SortUtils.swap(arrays,begin,randomIndex);

        int v = arrays[begin];
        int ltLastIndex = begin;
        int noCheckLastIndex = end;
        int sameFirstIndex = begin;
        for (int i = begin + 1; i <= noCheckLastIndex; i++) {
            if(arrays[i] < v){
                SortUtils.swap(arrays,i,ltLastIndex+1);
                //System.out.print("i:"+i+"; ltLastIndex+1："+(ltLastIndex+1)+"==");
                ltLastIndex ++;
            }else if(arrays[i] > v){
                SortUtils.swap(arrays,i,noCheckLastIndex);
                //System.out.print("i:"+i+"noCheckLastIndex："+noCheckLastIndex+"==");
                noCheckLastIndex--;
                i--;
            }
            //SortUtils.print(arrays);
        }
        SortUtils.swap(arrays,begin,ltLastIndex);
        //SortUtils.print(arrays);
        //System.out.println("========begin:"+begin+"\r\nend:"+end+"\r\nltLastIndex:"+ltLastIndex+"\r\nnoCheckLastIndex:"+noCheckLastIndex);
        deal3(arrays,begin,ltLastIndex-1);
        deal3(arrays,noCheckLastIndex,end);
    }
}
